package parser.ll;

import java.util.*;

/**
 * LL(1)语法分析器实现
 * 用于解析简单算术表达式，支持标识符(i)、加法(+)、乘法(*)及括号()
 * 语法规则:
 * E -> TE'
 * E'-> +TE' | ε
 * T -> FT'
 * T'-> *FT' | ε
 * F -> (E) | i
 */
public class LL1Analysis {
    // 待解析的输入字符串，以'#'作为结束符
    static String input = "i+i#";
    // 当前字符在输入字符串中的位置索引
    static int pos = 0;
    // 当前正在处理的字符
    static char currentChar = input.charAt(pos);
    // 步骤编号
    static int stepNo = 1;
    // 符号栈，初始时放入结束符'#'和开始符号'E'
    static Stack<Character> stack = new Stack<>();
    // 预测分析表，用于根据当前栈顶符号和当前输入字符选择产生式
    static Map<Character, Map<Character, String>> parsingTable = new HashMap<>();

    public static void main(String[] args) {
        // 初始化预测分析表
        initParsingTable();
        // 初始化符号栈
        stack.push('#');  // 栈底符号
        stack.push('E');  // 开始符号
        
        System.out.println("步骤\t\t符号栈\t\t当前输入\t\t动作");
        System.out.println("----------------------------------------------------------");
        
        // 开始LL(1)分析
        while (!stack.isEmpty()) {
            printStep();  // 打印当前步骤
            char top = stack.peek();  // 获取栈顶符号
            
            // 如果栈顶符号是终结符或'#'
            if (top == '+' || top == '*' || top == '(' || top == ')' || top == 'i' || top == '#') {
                if (top == currentChar) {
                    // 栈顶符号与当前输入字符匹配
                    stack.pop();  // 弹出栈顶符号
                    advance();    // 读取下一个输入字符
                } else {
                    // 匹配失败，报错
                    System.out.println("ERROR: 符号不匹配，期望" + top + "，实际得到" + currentChar);
                    return;
                }
            } else {
                // 栈顶符号是非终结符，查找预测分析表
                Map<Character, String> productionMap = parsingTable.get(top);
                String production = (productionMap != null) ? productionMap.get(currentChar) : null;
                
                if (production != null) {
                    // 找到对应的产生式
                    stack.pop();  // 弹出栈顶非终结符
                    
                    // 将产生式右部符号逆序压入栈中（ε不压入）
                    if (!production.equals("ε")) {
                        // 处理产生式右部，将特殊非终结符（如E'、T'）转换为内部表示
                        if (production.equals("TE'")) {
                            stack.push('e'); // E'用e表示
                            stack.push('T');
                        } else if (production.equals("+TE'")) {
                            stack.push('e'); // E'用e表示
                            stack.push('T');
                            stack.push('+');
                        } else if (production.equals("FT'")) {
                            stack.push('t'); // T'用t表示
                            stack.push('F');
                        } else if (production.equals("*FT'")) {
                            stack.push('t'); // T'用t表示
                            stack.push('F');
                            stack.push('*');
                        } else if (production.equals("(E)")) {
                            stack.push(')');
                            stack.push('E');
                            stack.push('(');
                        } else if (production.equals("i")) {
                            stack.push('i');
                        }
                    }
                } else {
                    // 预测分析表中无对应产生式，报错
                    System.out.println("ERROR: 无法找到对应产生式，非终结符" + top + "，输入字符" + currentChar);
                    return;
                }
            }
        }
        
        // 分析成功
        System.out.println("SUCCESS: 输入字符串符合语法规则");
    }
    
    /**
     * 初始化预测分析表
     * 预测分析表[非终结符][终结符] = 产生式右部
     */
    static void initParsingTable() {
        // 初始化非终结符的产生式映射
        Map<Character, String> E = new HashMap<>();
        Map<Character, String> EPrime = new HashMap<>();
        Map<Character, String> T = new HashMap<>();
        Map<Character, String> TPrime = new HashMap<>();
        Map<Character, String> F = new HashMap<>();
        
        // 填充预测分析表
        // E的产生式: E -> TE'
        E.put('(', "TE'");
        E.put('i', "TE'");
        
        // E'的产生式: E' -> +TE' | ε
        EPrime.put('+', "+TE'");
        EPrime.put(')', "ε");
        EPrime.put('#', "ε");
        
        // T的产生式: T -> FT'
        T.put('(', "FT'");
        T.put('i', "FT'");
        
        // T'的产生式: T' -> *FT' | ε
        TPrime.put('*', "*FT'");
        TPrime.put('+', "ε");
        TPrime.put(')', "ε");
        TPrime.put('#', "ε");
        
        // F的产生式: F -> (E) | i
        F.put('(', "(E)");
        F.put('i', "i");
        
        // 将非终结符映射添加到预测分析表中
        parsingTable.put('E', E);
        parsingTable.put('e', EPrime); // 使用小写e表示E'
        parsingTable.put('T', T);
        parsingTable.put('t', TPrime); // 使用小写t表示T'
        parsingTable.put('F', F);
    }
    
    /**
     * 移动到下一个字符
     * 若当前字符不是结束符'#'，则pos+1并更新当前字符currentChar
     */
    static void advance() {
        if (currentChar != '#' && pos < input.length() - 1) {
            pos++;
            currentChar = input.charAt(pos);
        }
    }
    
    /**
     * 打印当前分析步骤
     */
    static void printStep() {
        // 构建栈的字符串表示（为了美观，反序输出）
        StringBuilder stackStr = new StringBuilder();
        for (char c : stack) {
            // 特殊处理非终结符的显示
            if (c == 'e') {
                stackStr.append("E'");
            } else if (c == 't') {
                stackStr.append("T'");
            } else {
                stackStr.append(c);
            }
        }
        
        // 获取剩余输入部分
        String remainingInput = input.substring(pos);
        
        // 格式化输出当前步骤
        System.out.printf("%-8d%-16s%-16s", stepNo++, stackStr, remainingInput);
        
        // 确定当前动作
        char top = stack.peek();
        if (top == currentChar && top == '#') {
            System.out.println("接受");
        } else if (top == '+' || top == '*' || top == '(' || top == ')' || top == 'i' || top == '#') {
            if (top == currentChar) {
                System.out.println("匹配 " + top);
            } else {
                System.out.println("错误: 不匹配");
            }
        } else {
            // 查找并显示当前使用的产生式
            Map<Character, String> productionMap = parsingTable.get(top);
            String production = (productionMap != null) ? productionMap.get(currentChar) : null;
            
            // 根据非终结符显示对应的产生式
            String nonTerminal = "";
            if (top == 'E') nonTerminal = "E";
            else if (top == 'e') nonTerminal = "E'";
            else if (top == 'T') nonTerminal = "T";
            else if (top == 't') nonTerminal = "T'";
            else if (top == 'F') nonTerminal = "F";
            
            System.out.println(nonTerminal + "->" + (production != null ? production : "错误"));
        }
    }
}